﻿// 2-3 KK的传言 (15分).cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
// 7 公路村村通 (15分).cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
/*2-3 KK的传言 (15分)
股票经纪人KK想要在一群人（n个人的编号为0~n-1）中散布一个传言，传言只通过认识的人进行传递，在两个认识的人之间传递消息所需要的时间各有不同，在一群人中，KK想要找出以哪个人为起点开始传递这个传言，可以在耗时最短的情况下认所有人都收到消息。 请编写程序帮KK解决这个问题。

输入格式:
先输入n m，其中n是人数，m是可传递消息的人群关系数量，以下m行分别输入a b t ,表示 a 向 b 可传递消息，消耗的时间为t。 当输入0时，表示输入结束。

输出格式:
输出从第几个人开始传递传言耗时最短。如果无解，就输出-1。

输入样例:
在这里给出一组输入。例如：

4 4
0 1 2
0 2 5
0 3 1
2 3 3
6 5
0 1 2
0 2 5
0 3 1
2 3 3
4 5 2
0


输出样例:
在这里给出相应的输出。例如：

3
-1*/
/*date:2020.05.12 time: 22:31 PM
//user:dongcheng li
//level:7 说实话，把学期初的公路村村通代码改一下就好了，基本都是在输入的地方做改动即可。
//key:1.
	  2.由于测试案例不完备，没有说清楚最短耗费路径的起点和终点到底选择哪个，坑。
*/

#include <iostream>
using namespace std;
const int ban = 999999;//若两点之间没有道路
int digui(int** a, int k, int m, int n) {
	int i, j, next, h, l, distance;
	int min;
	int total = 0;
	int flag = 1;
	//新建一个记录数组visited
	int* visited = new int[m];
	for (i = 0; i < m; i++)
	{
		visited[i] = 0;//未访问是0
	}

	visited[k] = 1;
	int start = 0;
	if (n < m - 1) { return -1; }
	else {
		while (1)
		{
			min = ban;
			for (j = 0; j < m; j++)
			{
				if (a[k][j] < min && visited[j] == 0)
				{
					min = a[k][j];
					next = j;//记录最短值指向的点;
				}
			}
			//cout << "花费" << min << endl;
			//cout << "指向" << next << endl;
			start++;

			total = min + total;
			if (start < m - 1 && min == ban)
			{
				flag = 0;
				break;
			}
			if (start == m - 1)
			{
				break;
			}
			visited[k] = 1;
			int normal = 1;
			/*for (i = 0; i < m; i++)
			{
				if (visited[i] == 0)
				{
					normal = 0;
				}
			}
			if (normal == 1)//一个未被检查点都没有了
			{
				break;
			}*/
			k = next;


		}
		if (flag == 1) {
			return  total;
		}
		else
		{
			return -1;
			//cout << "-1";
		}
	}
}
int main()
{
	int m;
	while (1) {
		cin >> m;
		if (m != 0)
		{
			int i, j, k, next, n, h, l, distance;
			int min;


			//输入行列和道路数
			cin >> n;
			//建立行列相等的二维数组
			int** a = new int* [m];

			for (i = 0; i < m; i++)
			{
				a[i] = new int[m];
			}
			//对角线无穷化
			for (i = 0; i < m; i++)
			{
				for (j = 0; j < m; j++)
				{
					a[i][j] = ban;
				}//最开始每一个值默认距离为无穷，因为样例一开始给的矩阵是除对角线外都有值，忘记考虑不满矩阵的情况了
			}
			//输入每一条道路的距离
			for (i = 0; i < n; i++)
			{
				cin >> h;
				cin >> l;
				cin >> distance;
				a[h][l] = distance;
				a[l][h] = distance;


			}
			//开始遍历，以0点开始
			int lim = 999999;
			int k_min;
			for (k = 0; k < m; k++)
			{
				//cout << digui(a, k, m, n)<<endl;
				if (digui(a, k, m, n) <= lim && digui(a, k, m, n) != -1)//这里的相等很重要，决定了会输出后一点的哪个人
				{
					lim = digui(a, k, m, n);
					k_min = k;
				};
			}
			if (lim < 999999) {
				cout << k_min + 1;
			}
			else {

				cout << "-1";

			}
			cout << "\n";
		}
		else
		{
			return 0;
		}
	}
}



